1. Field of the Invention
The present invention relates to a technique of acquiring the position and orientation of a target object having a three-dimensional shape.
2. Description of the Related Art
There is available a technique called Model-Based Vision which obtains the correspondence between a three-dimensional point acquired from the surface position of a target object by range imaging or the like and a geometrical feature extracted from a three-dimensional shape model of the target object and estimates the position and orientation of the target object by using the distance between the correspondent points as an evaluation function. This technique requires a three-dimensional shape model of a target object in advance to estimate position and orientation parameters. Methods of obtaining such three-dimensional shape models include a method using the design data obtained by CAD software and a method using a polygon model imitating (approximating) the shape of a target object.
CAD data representing the shape of an object expresses the shape by combining a plurality of partial shapes expressed by parameters. Each partial shape is constituted by a surface and a curve defining the contour of the surface. Each surface is expressed by an analytical curved surface such as a circular cone or torus curved surface, or a free curved surface such as a B-Spline curved surface or NURBS curved surface. The surface expressed by these parameters has a merit of being capable of expressing a complex curved surface shape with a small amount of information. Therefore, geometrical features on a model can be calculated with high accuracy in estimation of the position and orientation of an object by using the parameters for each surface which CAD data has, and thus an accurate processing will be enabled. This makes it possible to perform processing with high accuracy. On the other hand, this processing requires complex geometrical calculations for free curved surfaces such as NURBS curved surfaces when calculating points on surfaces or performing correspondence search with three-dimensional points. In addition, when performing inside/outside determination with respect to a contour line, it is necessary to perform complex calculations, resulting in a long processing time.
On the other hand, a polygon model expresses an object shape by a combination of polygonal surfaces. A polygon model allows the calculation of points on surfaces and correspondence search using three-dimensional points with simple geometrical calculations, and has a merit of being low in calculation load. In contrast to this, since an object shape is polygonally approximated, a difference occurs between the object shape and the model. There is available a method of reducing this difference by approximating a surface with a set of very small polygons. However, the total number of polygons required exponentially increases as an allowable difference decreases.
As countermeasures against problems in the respective models, there are available methods of implementing high-speed, accurate processing by combining a model expressed by parameters such as CAD data and a polygon model.
For example, Japanese Patent Laid-Open No. 2009-020671 discloses a method of holding, in advance, a model comprising a combination of parameters expressing a curved surface shape and a polygon model approximating the shape, and using that in calculating a distance value from the reference surface to the curved surface shape with respect to each vertex of a lattice on the reference surface. This method derives the coordinates of the intersection points between polygons and straight lines extending from the respective lattice points vertically to a reference surface, and then calculates the distances from the intersection points to a curved surface shape from curved surface parameters, thereby correcting the distances from the vertices to the curved surface shape.
When calculating the distances between the respective lattice points on a reference surface and a curved surface, the above method calculates coarse distances via polygons at high speed first, and then modifies the coarse distances by calculating accurate distances to the curved surface associated with the polygons from curved surface parameters, thereby satisfying both the requirements for high speed and high accuracy. This method obtains the correspondence relationship between the respective lattice points on a reference surface and a model. However, the method does not perform correspondence search with points in an arbitrary three-dimensional space, and hence cannot be directly applied to the positioning between the model and the three-dimensional points obtained from a range image of the target object.